1. Technical Field
The present invention is directed to an apparatus and method for reconstructing missing data using cross-parity stripes on storage media. Specifically, the invention is directed to the use of a plurality of cross-parity stripes on storage media to correct for errors in reading the data on the storage media.
2. Description of Related Art
The use of parity stripes to correct up to three read errors on magnetic tape is generally known in the art. For example, U.S. Pat. No. 4,201,976 issued to Arvind M. Patel, and the article by the same author entitled xe2x80x9cAdaptive cross-parity (AXP) Code for a High-Density Magnetic Tape Subsystem,xe2x80x9d IBM J. Res. Develop., vol. 29, no. 6, November 1985, describe a method for using vertical and cross parity stripes to correct data bits on a single magnetic tape for up to three stripe read errors. These documents are hereby incorporated by reference.
Additionally, it is generally known to use redundant array of independent tape (RAIT) systems. RAIT systems use a plurality of tape drives to improve the performance and reliability of the storage medium. Data may be striped across many tape drives to increase performance. However, the drawback is that any tape error renders the complete stripe group unreadable.
Thus, it would be advantageous to develop an apparatus and method that is capable of correcting for more than three stripe read errors when reading data from a storage medium. Furthermore, it would be advantageous to develop an apparatus and method for correcting more than three stripe read errors when reading data from a RAIT system.
The present invention provides an apparatus and method for reconstructing missing data using cross-parity stripes on a storage medium. The apparatus and method may operate on data symbols having sizes greater than a data bit, such as may be used in a RAIT system.
The apparatus and method makes use of a plurality of parity stripes for reconstructing missing data stripes. The parity symbol values in the parity stripes are used as a basis for determining the value of the missing data symbol in a data stripe.
With the apparatus and method of the present invention, a correction matrix is shifted along the data stripes, correcting missing data symbols as it is shifted. The correction is performed from the outer most data stripes towards the inner data stripes to thereby use previously reconstructed data symbols to reconstruct other missing data symbols.
Thus, with the present invention data is reconstructed by organizing the received parity stripes in order. The smallest slope diagonal lines of the correction matrix, representing the linear equations of the parity symbols, may be used to correct the top and bottom most missing data stripes as deep as is necessary. Once the top and bottom most data stripes are corrected, the next largest slope lines may be used to correct the next inner missing data stripe and so forth until all the missing data stripes are corrected.